﻿namespace Homework20
{
    using System;
    using System.Collections.Generic;

    class Program
    {/// <summary>
    /// 最短路问题
    /// </summary>
        public class Graph
        {
            public int VertexCount { get; private set; }
            public Dictionary<int, List<(int, int)>> AdjList { get; private set; }

            public Graph(int vertexCount)
            {
                VertexCount = vertexCount;
                AdjList = new Dictionary<int, List<(int, int)>>();
                for (int i = 0; i < vertexCount; i++)
                {
                    AdjList[i] = new List<(int, int)>();
                }
            }

            /// <summary>
            /// 添加边
            /// </summary>
            /// <param name="src"></param>
            /// <param name="dest"></param>
            /// <param name="weight"></param>
            public void AddEdge(int src, int dest, int weight)
            {
                AdjList[src].Add((dest, weight));
            }
        }
        /// <summary>
        /// 执行算法
        /// </summary>
        /// <param name="graph"></param>
        /// <param name="source"></param>
        /// <param name="target"></param>
        public static void Dijkstra(Graph graph, int source, int target)
        {
            int[] dist = new int[graph.VertexCount];
            bool[] visited = new bool[graph.VertexCount];
            int[] prev = new int[graph.VertexCount]; // 用于记录路径

            for (int i = 0; i < graph.VertexCount; i++)
            {
                dist[i] = int.MaxValue;
                visited[i] = false;
                prev[i] = -1;
            }

            dist[source] = 0;

            for (int count = 0; count < graph.VertexCount; count++)
            {
                int u = MinDistance(dist, visited);

                if (u == -1) break;

                visited[u] = true;

                foreach (var neighbor in graph.AdjList[u])
                {
                    int v = neighbor.Item1;
                    int weight = neighbor.Item2;

                    if (!visited[v] && dist[u] + weight < dist[v])
                    {
                        dist[v] = dist[u] + weight;
                        prev[v] = u;
                    }
                }
            }

            // 打印从源点到目标节点的路径
            if (dist[target] != int.MaxValue)
            {
                Console.WriteLine($"从源点 {source} 到节点 {target} 的最短路径长度为 {dist[target]}");
                PrintPath(prev, source, target);
            }
            else
            {
                Console.WriteLine($"从源点 {source} 到节点 {target} 没有路径");
            }
        }

        private static int MinDistance(int[] dist, bool[] visited)
        {
            int min = int.MaxValue;
            int minIndex = -1;

            for (int i = 0; i < dist.Length; i++)
            {
                if (!visited[i] && dist[i] < min)
                {
                    min = dist[i];
                    minIndex = i;
                }
            }

            return minIndex;
        }

        private static void PrintPath(int[] prev, int source, int target)
        {
            Stack<int> path = new Stack<int>();
            for (int at = target; at != -1; at = prev[at])
            {
                path.Push(at);
            }

            Console.Write("路径：");
            foreach (int node in path)
            {
                Console.Write(node + " ");
            }
            Console.WriteLine();
        }
        /// <summary>
        /// 输入图
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            Graph graph = new Graph(6);
            graph.AddEdge(0, 1, 250); // v1到v2的权重为250
            graph.AddEdge(0, 2, 400); // v1到v3的权重为400
            graph.AddEdge(1, 2, 100); // v2到v3的权重为100
            graph.AddEdge(1, 3, 300); // v2到v4的权重为300
            graph.AddEdge(2, 4, 275); // v3到v5的权重为275
            graph.AddEdge(2, 3, 150);//v3到v4的权重未150
            graph.AddEdge(3, 4, 100); // v4到v5的权重为100
            graph.AddEdge(3, 5, 200); // v4到v6的权重为200
            graph.AddEdge(4, 5, 150); // v5到v6的权重为150

            Dijkstra(graph, 0, 5);
        }
    }
}